Processing math: 100%
剑指 Offer 34. 二叉树中和为某一值的路径

题目描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1:

plaintext
1
2
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]

示例 2:

plaintext
1
2
输入:root = [1,2,3], targetSum = 5
输出:[]

示例 3:

plaintext
1
2
输入:root = [1,2], targetSum = 0
输出:[]

提示:

  • 树中节点总数在范围 [0,5000]
  • 1000<=Node.val<=1000
  • 1000<=targetSum<=1000

注意:本题与主站 113 题相同:https://leetcode-cn.com/problems/path-sum-ii/


算法

(递归,前序遍历) O(n)

使用前序遍历的顺序遍历二叉树,遍历一个节点将其加入到路径数组 path 中,如果当前节点是叶子节点且路径和 sum+root>val=target,则说明在树中找到了一条满足路径,将当前路径加入到答案中,继续递归处理左子树和右子树,最后不要忘了 path 数组回溯。

时间复杂度

O(n)

空间复杂度

最坏情况下,叶子节点的个数为 O(2n1),其中 n 是二叉树的层数,每个叶子节点对应一个方案,每个方案上的节点个数是 n,所以总时间复杂度为 O(n2n1)

C++ 代码

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> ans;
vector<int> path;

void dfs(TreeNode* root, int sum, int target) {
if (!root) return;
path.push_back(root->val);
if (!root->left && !root->right && sum + root->val == target) {
ans.push_back(path);
}

dfs(root->left, sum + root->val, target);
dfs(root->right, sum + root->val, target);
path.pop_back();
}

vector<vector<int>> pathSum(TreeNode* root, int target) {
if (!root) return ans;
dfs(root, 0, target);
return ans;
}
};
Author: tonngw
Link: https://tonngw.com/2022/07/08/剑指 Offer/剑指 Offer 34. 二叉树中和为某一值的路径/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Powered By Valine
v1.5.2